package codetop.dp;

import org.junit.Test;

public class Code032 {
    @Test
    public void test(){
        System.out.println(longestValidParentheses("()(())"));
    }

    public int longestValidParentheses(String s) {
        int len=s.length();
        int []dp=new int[len];
        int max=0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i)==')'){
                if (s.charAt(i-1)=='('){
                    dp[i]=(i >= 2 ?dp[i-2]:0)+2;
                }else if (i-dp[i-1]>0&&s.charAt(i-dp[i-1]-1)=='('){
                    dp[i]=dp[i-1]+((i-dp[i-1])>=2?dp[i-dp[i-1]-2]:0)+2;
                }
                max=Math.max(max,dp[i+1]);
            }
        }
        return max;
    }
}
